package greed;

import java.util.Arrays;

/**
 * @author wcj
 * @Date 2021/7/6 22:12
 * @Version 1.0
 */
public class Allocation {

    /**
     * 有一群孩子和一堆饼干：每个孩子有饥饿值，每块饼干有饱腹值，一个孩子只能吃一块饼干，且饱腹值>=饥额值才能吃饱，问最多有多少个孩子可以吃饱
     * ①贪心策略：什么情况下能让最多的孩子吃饱，实际上就是做到饼干的最优分配，类似于可变分区算法中的最佳适配算法，把刚好满足孩子的饼干给他吃，
     * 并且从饥饿值最小的孩子开始喂。
     *
     * @param children
     * @param cookie
     * @return
     */
    public static int greed(int[] children, int[] cookie) {
        Arrays.sort(children);
        Arrays.sort(cookie);
        int child = 0;
        int cook = 0;
        while (child < children.length && cook < cookie.length && children[child] <= cookie[cook++]) {
            child++;
        }
        return child;
    }
}
